package DP.Lesson7;

import java.util.List;

/**
 * https://www.lintcode.com/problem/minimum-adjustment-cost/description
 * 不小于100，并且这个最小修改代价是按照差值来的，不是按照次数来的
 */
public class MinimunAdjustCost {


    public int MinAdjustmentCost(List<Integer> A, int target) {
        int n = A.size();
        if(n==0) return 0;
        int[][] dp = new int[n + 1][101];//第i个数改成对应数值的修改成本
        //初始化，获得第一行的数，调整到 1--100 之间的各个代价是啥
        for(int i=1; i<=100; i++) dp[1][i] = Math.abs(A.get(0) - i);

        for(int i=2; i<=n; i++){//第一个数已经计算出来了，所以从第二个开始
            for(int j=1; j<=100; j++){//看这个数从1、100之间的每种选择是咋样的
                dp[i][j] = Integer.MAX_VALUE;

                //下面这个循环是获取上一个数字做调整的最小值
                //为什么，k是取 j-target  和 j+target的范围呢？
                //要在j-target里面遍历，是因为 在 j-target 之外遍历，就满足不了题目要求
                //比如，j=4，目标是1，那么,   在4这个位置，我只需要看 3、4、5 就可以了， 1、2、6、7、8都都满足不了的
                //这一行的数，调整为 j的时候，我要看上一行 在j 这个范围内的数，哪个 移动的最少
                //这里要背下来，多画一画，画了二维数组就理解了。
                for(int k=j-target; k <= j+target; k++){
                    if(k<1 || k>100) continue;;
                    dp[i][j] = Math.min(dp[i][j], dp[i-1][k]);
                }
                dp[i][j] += Math.abs(j-A.get(i-1));
            }
        }

        int res = Integer.MAX_VALUE;
        for(int i=1; i<=100; i++){
            res = Math.min(res,dp[n][i]);
        }

        return res;
    }



    public static void main(String[] args){
        int[] n = new int[]{-1,1,1,1};

    }


}
